//https://leetcode.cn/problems/maximum-value-at-a-given-index-in-a-bounded-array/submissions/565920329/
class Solution {
public:
    int maxValue(int n, int index, int maxSum) { 
        int l = 1, r = maxSum, mid, ans = 0;
        
        auto sum_part = [](int x, int length) -> long long {
            if (x > length) {
                return (long long)(x + (x - length + 1)) * length / 2;
            } else {
                return (long long)(x + 1) * x / 2 + (length - x);
            }
        };

        auto f = [&](int x) -> bool {
            return sum_part(x - 1, index)+sum_part(x - 1, n - index - 1) + x <= maxSum;
        };  

        while (l <= r) {
            mid = (l + r) >> 1;
            if (f(mid)) {
                ans = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }   
        }
        return ans;
    }
};